import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;

public class Board {

    private int moves;
    private Board prev;
    private int i0, j0;
    private int[][] blocks;
    private int N;

    public Board(int[][] blocks) {
        this.N = blocks.length;
        this.blocks = new int[N][];
        for (int i = 0; i < N; i++) {
            assert N == blocks[i].length;
            this.blocks[i] = new int[N];
            for (int j = 0; j < N; j++) {
                this.blocks[i][j] = blocks[i][j];
                if (0 == this.blocks[i][j]) {
                    this.i0 = i;
                    this.j0 = j;
                }
            }
        }
    }

    public int dimension() {
        return N;
    }

    public int hamming() {
        int hamming = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int b = this.blocks[i][j];
                if (b != 0) {
                    int bj = (b - 1) % N;
                    int bi = (b - 1) / N;
                    if (bj != j || bi != i) hamming++;
                }
            }
        }
        return hamming + this.moves;
    }

    public int manhattan() {
        int manhattan = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int b = this.blocks[i][j];
                if (b != 0) {
                    int bj = (b - 1) % N;
                    int bi = (b - 1) / N;
                    manhattan += Math.abs(bi - i) + Math.abs(bj - j);
                }
            }
        }
        return manhattan + this.moves;
    }

    public boolean isGoal() {
        int k = 1;
        for (int[] rows : this.blocks) {
            for (int block : rows) {
                if (!(((k++) % (N * N)) == block)) {
                    return false;
                }
            }
        }
        return true;
    }

    public Board twin() {
        Board twin = new Board(this.blocks);
        if (1 == N) {
            return twin;
        }
        int i = (i0 == 0) ? N-1 : 0;
        int j = 0;
        int temp = twin.blocks[i][j];
        twin.blocks[i][j] = twin.blocks[i][j + 1];
        twin.blocks[i][j + 1] = temp;
        return twin;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Board board = (Board) o;

        if (board.blocks.length != this.blocks.length) return false;

        for (int i = 0; i < this.blocks.length; i++) {
            if (!Arrays.equals(this.blocks[i], board.blocks[i])) return false;
        }
        return true;
    }

    public Iterable<Board> neighbors() {
        Collection<Board> neighbors = new ArrayList<Board>(4);
        Board n;
        if (0 != i0) {
            n = new Board(this.blocks);
            n.blocks[i0][j0] = n.blocks[i0-1][j0];
            n.blocks[i0-1][j0] = 0;
            n.i0 -= 1;
            n.prev = this;
            n.moves = this.moves + 1;
            if (!n.equals(prev)) neighbors.add(n);
        }
        if (N-1 != i0) {
            n = new Board(this.blocks);
            n.blocks[i0][j0] = n.blocks[i0+1][j0];
            n.blocks[i0+1][j0] = 0;
            n.i0 += 1;
            n.prev = this;
            n.moves = this.moves + 1;
            if (!n.equals(prev)) neighbors.add(n);
        }
        if (0 != j0) {
            n = new Board(this.blocks);
            n.blocks[i0][j0] = n.blocks[i0][j0-1];
            n.blocks[i0][j0-1] = 0;
            n.j0 -= 1;
            n.prev = this;
            n.moves = this.moves + 1;
            if (!n.equals(prev)) neighbors.add(n);
        }
        if (N-1 != j0) {
            n = new Board(this.blocks);
            n.blocks[i0][j0] = n.blocks[i0][j0+1];
            n.blocks[i0][j0+1] = 0;
            n.j0 += 1;
            n.prev = this;
            n.moves = this.moves + 1;
            if (!n.equals(prev)) neighbors.add(n);
        }
        return neighbors;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(N).append("\n");
        for (int[] rows : this.blocks) {
            for (int block : rows) {
                sb.append(block).append(" ");
            }
            sb.append("\n");
        }
        return sb.toString();
    }

}
